1. Field of the Invention
This invention relates to computer systems and more particularly to a system and method for maintaining data synchronization among software tasks.
2. Background Information
A computer system can roughly be divided into the following parts: hardware, operating system, application programs, and users. The hardware provides the basic computing resources. The application programs utilize these resources to solve problems for the users. The operating system provides an environment within which the application programs can run as software tasks to do useful work. An operating system can be designed to run only one software task at a time, or it may be capable of running multiple software tasks at a time concurrently. A typical operating system comprises a kernel which is usually made up of a series of software routines, often called “kernel routines,” that typically handle certain low-level tasks such as, e.g., memory allocation, processing input/output (I/O)-device requests, processing hardware trap conditions, and scheduling software tasks.
The operating system typically runs in a mode known as “kernel mode,” and the software tasks typically run in a mode known as “user mode.” The kernel mode is typically a privileged mode of operation, in which the software is granted full access to the system resources. Software operating in user mode, on the other hand, is often granted only limited or no direct access to the system resources. To gain access to a restricted resource, software running in user mode typically calls a kernel routine.
A multiprogramming operating system provides an environment in which several application programs can run in the computer system concurrently. In this context, each such separate program is referred to as a different “process.” A process is a program in execution. Since only one concurrently running process can actually be executing at any given time in a uniprocessor system, concurrency is typically achieved in such systems by assigning time slots to different processes and scheduling processes to take control of the processor for their respective time slots. Scheduling is often handled by a separate operating-system functional section called a scheduler, which is typically part of the operating system's kernel.
When a given process reaches the end of its assigned time slot, the scheduler preempts that process. The operating system takes control of the processor from the process and gives it to the next process to be scheduled.
Preemption is typically performed as follows. When the time slot ends for a running process, the processor switches to kernel mode, an interrupt is generated, and control of the processor is turned over to the operating system. The operating system saves the process's execution context, i.e., saves various run-time state associated with the process, and its scheduler schedules the next process to run in the system. Examples of state information that is often part of the execution context are items such as the memory map, general-purpose-register values, various system-register values, processor status words (PSWs), the program-counter (PC) value, in some architectures the next-program-counter (nPC) value, and stack information, including the contents of the run-time stack. The program counter points to the instruction that is to be executed when the process resumes execution. For reasons that will be explained below, the next program counter points to the instruction to be executed after the instruction pointed to by the program counter.
Once the scheduler selects the next process to be run, it restores any saved context associated with the process, assigns it a time slot, switches from kernel mode to user mode, and grants control of the processor to the selected process. The operation of saving one software task's context and replacing it with another's is known as a context switch.
In some multiprogramming operating systems, the concept of time sharing among processes is extended further to include the notion of sharing among threads of execution (“threads”) of the same process. Just as different processes are different programs that in a multiprogramming operating system are executed concurrently, different threads are different concurrently executing flows of control within a process.
Typically, operating systems that support threads are organized in such a manner that each individual thread running in the system has its own separate execution context. A thread's execution context is like a process's, but, whereas different processes typically have different memory maps, different threads of the same process do not. And an operating system's scheduling of threads is similar to its scheduling of processes; whenever a thread reaches the end of its time slot, the operating system halts the thread's execution, selects the next thread for execution, restores its execution context, and hands control of the processor to the selected thread. The selected thread then resumes execution at the instruction pointed to by the saved PC value.
Since threads within a multithreaded process usually share a single address space, a process's different threads typically can read and write the same memory locations. This can sometimes give rise to consistency problems. Suppose, for example, a data object represents a bank-account balance and that multiple threads employ a critical section of code to make additions to the account. The code directs the thread to read the shared object, add the deposit value to the value that is read, and write the result back into the object. Now suppose a first thread is executing this code section and reaches the end of its assigned time slot just after it has read the object. Further assume that a second thread is then scheduled and manages to complete enough of that code section to read the object, calculate a new value, and write the new value back into the object. In the absence of a mechanism for what I will refer to below as a “synchronization,” the first thread will not be aware of the shared data object's new value when it is rescheduled, so it continues execution by basing calculation of its new value on the “old” value that was read and by writing the new data value into the shared data object. It thereby “destroys” the data value that was written by the second thread. The data thus become inconsistent: it will be as though the deposit that the second thread was to perform did not happen.
To avoid such problems, multithreaded processes often employ various synchronization techniques. One synchronization approach employs “locking mechanisms.” Locking mechanisms basically control access to a shared data object by allowing a thread access to a shared data object only if the thread has a “lock” associated with the object. In such a scheme, a thread must first acquire the lock before it accesses the data object. A lock is typically a field that is associated with a data object and indicates whether a thread is already in possession of the object. In a mutual-exclusion arrangement, the operating system grants the lock to a thread only if no other thread is currently in possession. A thread that has the lock can safely manipulate the data object without interference from other threads.
Locking mechanisms provide a simple yet effective way to synchronize access to shared data. But program code must be carefully designed so as to avoid problems associated with locking mechanisms, such as “starvation” or “deadlock.” Starvation occurs when one or more threads are blocked from gaining access to a resource because another thread has control of that resource. The blocked threads are said to be “starved” because they cannot gain access to the locked resource and thus cannot make progress.
To understand deadlocks, consider an example in which a shared data area contains two data objects named O1 and O2. Further assume that each object has only one lock associated with it. Now suppose that thread T1 acquires the lock on O1 and thread T2 acquires the lock on O2. Further assume that thread T1 is at a point in its code where it needs the lock on O2 before it can continue to a point at which it can release its lock on O1. Likewise assume that thread T2 is at a point in its code where it needs the lock on O1 before it can continue to the point at which it releases the lock on O2. Since T2 cannot release the lock on O2 until T1 releases the lock on O1, but T1 cannot release the lock on O1 until T2 releases the lock on O2, the threads are deadlocked: neither can continue. Deadlock situations can be avoided by carefully crafting the code to ensure that locks are always acquired in the same order. But this may not be a practical solution in complex systems that employ many thousands of locks.
One synchronization approach that does not use locks and thus avoids some of their drawbacks uses a restartable atomic sequence (“RAS”) to ensure data consistency. A RAS is a section of code so written that executing it from the beginning eliminates any inconsistency that might otherwise result from preemption in the middle of its execution. Synchronization approaches that utilize RASs often employ a “signal” mechanism that informs the code that a context switch has occurred and that atomic execution of the critical section may therefore have been compromised. A signal is a communication sent between the kernel and a software task that communicates the occurrence of certain events external to the task, such as the rescheduling of a process while in a critical code section. A signal can take many forms. For example, a signal can be a bit that is set in a processor status word (PSW), or a code that is placed on the software task's stack, or a data value that is placed in a particular shared memory location, or a call to a signal handler associated with the task. In response to the signal, the software task typically determines whether it is in a section of code that is to be executed in an atomic manner. If so, the software task restarts the code execution at the beginning of the RAS.
A synchronization technique that utilizes RAS and employs a signaling mechanism is described in commonly owned co-pending U.S. patent application Ser. No. 09/452,571 for a “Mutual Exclusion System and Method for Uniprocessor Digital Computer System” which was filed on Dec. 1, 1999, by David Dice. In that technique, an executing thread can arrange to be notified if it has been interrupted. The mechanism employed for this purpose is that the thread asserts what the application refers to as a non-restorable trap (NRT) indicator when it is in a critical-code section, i.e., in a code section whose preemption could lead to inconsistency. When the operating system restores the thread's state, it checks the NRT indicator. If it determines that the NRT indicator is set, the operating system traps, and a trap handler that processes the trap causes a signal to be delivered to the thread. When the thread resumes execution, it receives the signal and takes whatever corrective measures are deemed necessary, such as (in the case of an RAS) returning to the beginning of the critical section. If the NRT indicator is not set, on the other hand, the thread resumes where execution left off when the thread was last preempted.